Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. Problem from LeetCode



In [1]:

    
# Input
nums = [1,3,5,6,7,8,10]
target = 4



In [2]:

    
# Method1
def search_insert1(nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left, right = 0, len(nums)-1

        while left <= right:
            mid = (left + right) // 2
            if target <= nums[mid]:
                right = mid - 1            
            elif target > nums[mid]:
                left = mid + 1                
        return left



In [3]:

    
# Method2 
def search_insert2(nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        return len([i for i in nums if i < target])



In [4]:

    
# Output1
%time search_insert1(nums, target)









    



CPU times: user 8 µs, sys: 1 µs, total: 9 µs
Wall time: 15.7 µs






    Out[4]:





2



In [5]:

    
# Output2
%time search_insert2(nums, target)









    



CPU times: user 10 µs, sys: 1 µs, total: 11 µs
Wall time: 14.8 µs






    Out[5]:





2